<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script src="./js/DIctionary.js"></script>
    <script src="./js/Queue.js"></script>
    <script>
        // 一个图G = (V, E)由以下元素组成。
        //  V：一组顶点 
        //  E：一组边，连接V中的顶点

        class Graph {
            constructor() {
                this.vertices = [];
                this.adjList = new Dictionary();
            }

            // 添加顶点
            addVertex(v) {
                this.vertices.push(v);
                this.adjList.set(v, []);
            }

            // 创建边，连接顶点
            addEdge(v, w) {
                this.adjList.get(v).push(w);
                this.adjList.get(w).push(v);
            }

            // 控制台输出
            toString() {
                let str = '';

                for (let i = 0; i < this.vertices.length; i++) {
                    str += `${this.vertices[i]}=>`;

                    let neighbors = this.adjList.get(this.vertices[i])
                    for (let j = 0; j < neighbors.length; j++) {
                        str += `${neighbors[j]} `
                    }
                    str += '\n'
                }
                return str;
            }

            // 广度优先搜索

            // 将所有顶点变成白色
            initializeColor() {
                let color = {};
                for (let i = 0; i < this.vertices.length; i++) {
                    color[this.vertices[i]] = 'white';
                }

                return color;
            }

            bfc(v, callback) {
                let queue = new Queue(),
                    color = this.initializeColor();

                queue.enqueue(v);

                while (!queue.isEmpty()) {
                    let u = queue.dequeue(),
                        neighbors = this.adjList.get(u);

                    color[u] = 'gray';

                    for (let i = 0; i < neighbors.length; i++) {
                        let w = neighbors[i];
                        if (color[w] === 'white') {
                            color[w] = 'gray';
                            queue.enqueue(w);
                        }
                    }
                    color[u] = 'black';

                    if (callback) {
                        callback(u);
                    }
                }
            }

            // 最小路径
            BFC(v, callback) {
                let queue = new Queue(),
                    color = this.initializeColor(),
                    d = {},
                    pred = {};

                queue.enqueue(v);

                for (let i = 0; i < this.vertices.length; i++) {
                    d[this.vertices[i]] = 0;
                    pred[this.vertices[i]] = null;
                }

                while (!queue.isEmpty()) {
                    let u = queue.dequeue(),
                        neighbors = this.adjList.get(u);

                    color[u] = 'gray';

                    for (let i = 0; i < neighbors.length; i++) {
                        let w = neighbors[i];

                        if (color[w] === 'white') {
                            color[w] = 'gray';
                            d[w] = d[u] + 1;
                            pred[w] = u;
                            queue.enqueue(w);
                        }
                    }
                    color[u] = 'black';

                }
                return {
                    distance: d,
                    pred: pred,
                }
            }


            // 深度优先搜索
            dfs(callback){
                let color = this.initializeColor();

                for (let i = 0; i < this.vertices.length; i++) {
                    if(color[this.vertices[i]]==='white'){
                        this.dfsVisit(this.vertices[i], color, callback);
                    }
                }
            }

            dfsVisit(u,color,callback){
                color[u] = 'gray';
                if(callback){
                    callback(u);
                }

                let neighbors = this.adjList.get(u);

                for (let i = 0; i < neighbors.length; i++) {
                    let w = neighbors[i]
                   if(color[w]==='white'){
                       this.dfsVisit(w,color,callback);
                   }
                }

                color[u] = 'black';
            }
        }


        let graph = new Graph();
        let myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
        for (var i = 0; i < myVertices.length; i++) {
            graph.addVertex(myVertices[i]);
        }
        graph.addEdge('A', 'B');
        graph.addEdge('A', 'C');
        graph.addEdge('A', 'D');
        graph.addEdge('C', 'D');
        graph.addEdge('C', 'G');
        graph.addEdge('D', 'G');
        graph.addEdge('D', 'H');
        graph.addEdge('B', 'E');
        graph.addEdge('B', 'F');
        graph.addEdge('E', 'I');

        // console.log(graph.toString());

        // graph.bfc(myVertices[0], (u) => console.log('Visited vertex: ' + u))
        // console.log(graph.BFC(myVertices[0]));
        graph.dfs((u) => console.log('Visited vertex: ' + u))

    </script>
</body>

</html>